/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/count-of-smaller-number-before-itself
   @Language: C++
   @Datetime: 16-02-09 08:54
   */

// Method 1, Segment Tree, Time O(nlogn), Time 326ms
class Solution {
	struct SegTreeNode{
		int first, last, count;     // range of num val, not pos
		struct SegTreeNode *left, *right;
		SegTreeNode(int first, int last, int count){
			this->first = first;
			this->last = last;
			this->count = count;
			left = right = NULL;
		}
		~SegTreeNode(){
			if (left) delete left;
			if (right) delete right;
		}
	};
	SegTreeNode *build(int first, int last){
		if (first>last) return NULL;
		SegTreeNode *root = new SegTreeNode(first,last,0);
		if (first==last) return root;
		root->left = build(first,first+(last-first)/2);
		root->right = build(first+(last-first)/2+1,last);
		root->count = root->left->count + root->right->count;
		return root;
	}
	int query(SegTreeNode *root,int first,int last){
		if (first>last || root==NULL || root->count==0) return 0;
		if (root->first==first && root->last==last)
			return root->count;
		int mid = root->first+(root->last-root->first)/2;
		if (mid<first) return query(root->right,first,last);
		if (mid>=last) return query(root->left,first,last);
		return query(root->left,first,mid)+query(root->right,mid+1,last);
	}
	void insert(SegTreeNode *root, int val){
		if (root==NULL) return;
		if (root->first==root->last && root->first==val){
			++root->count;
			return;
		}
		int mid = root->first+(root->last-root->first)/2;
		if (mid>=val) insert(root->left,val);
		else insert(root->right,val);
		root->count = (root->left ? root->left->count:0)
			+ (root->right ? root->right->count:0);
	}
public:
	/**
	 * @param A: An integer array
	 * @return: Count the number of element before this element 'ai' is 
	 *          smaller than it and return count number array
	 *          range of val [0,10000]
	 */
	vector<int> countOfSmallerNumberII(vector<int> &A) {
		// write your code here
		vector<int> v(A.size());
		SegTreeNode *root = build(0,10000);
		for(int i=0; i<A.size(); ++i){
			v[i] = query(root,0,A[i]-1);
			insert(root,A[i]);
		}
		return v;
	}
};


// Method 2, Binary Search, Time O(logn!), Time 704ms
class Solution {
public:
	/**
	 * @param A: An integer array
	 * @return: Count the number of element before this element 'ai' is 
	 *          smaller than it and return count number array
	 *          range of val [0,10000]
	 */
	vector<int> countOfSmallerNumberII(vector<int> &A) {
		// write your code here
		if (A.size()<1) return {};
		vector<int> v(A.size(),0), B(1,A[0]);
		for(int i=0; ++i<A.size();){
			auto pos=lower_bound(B.begin(),B.end(),A[i]);
			v[i]=pos-B.begin();
			B.insert(pos,A[i]);
		}
		return v;
	}
};
